import java.util.Stack;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-06-22
 * Time: 20:23
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    
    public TreeNode(int val) {
        this.val = val;
        
    }
    
}
public class Solution2 {
    public TreeNode Convert(TreeNode pRootOfTree) {
        //非递归的方法，借用一个栈来辅助进行遍历
        if(pRootOfTree==null){
            return null;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode head=null;
        TreeNode pre=null;
        //设置一个布尔值，判断是不是第一个节点
        Boolean isFirst=true;
        while (pRootOfTree!=null || !stack.isEmpty()){
            while (pRootOfTree!=null){
                stack.push(pRootOfTree);
                pRootOfTree=pRootOfTree.left;
            }
            //遍历到了空节点，就把最近放入的节点弹出，作为头结点
            pRootOfTree=stack.pop();
            if(isFirst){
                //如果是第一个节点
                head=pRootOfTree;
                pre=pRootOfTree;
                isFirst=false;
            }else{
                //不是第一个节点
                pre.right=pRootOfTree;
                pRootOfTree.left=pre;
                pre=pRootOfTree;
            }
            pRootOfTree=pRootOfTree.right;
        }
        return head;
    }
}
